package _17_剑指Offer;

import java.util.Deque;
import java.util.LinkedList;
import java.util.Queue;

public class _59_剑指OfferII队列的最大值 {

    // 使用单调队列记录最大值
    private Deque<Integer> maxQueue = new LinkedList<>();

    private Queue<Integer> queue = new LinkedList<>();

    public _59_剑指OfferII队列的最大值() {

    }

    public int max_value() {
        if (queue.isEmpty()) return -1;
        return maxQueue.peekFirst();
    }

    public void push_back(int value) {
        // 弹出队列中比起小的元素
        while (!maxQueue.isEmpty() && value > maxQueue.peekLast()) {
            maxQueue.pollLast();
        }
        queue.offer(value);
        maxQueue.offer(value);
    }

    public int pop_front() {
        while (queue.isEmpty()) {
            return -1;
        }
        int value = queue.poll();
        if (value == maxQueue.getFirst()) {
            maxQueue.pollFirst();
        }
        return value;
    }

}
